package example.动态规划;

import java.util.HashMap;
import java.util.Map;

//https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/submissions/
public class Demo3 {
    public static ListNode getKthFromEnd(ListNode head, int k) {
        ListNode temp = head;
        ListNode prev = null;
        Map<Integer, ListNode> map = new HashMap<>();
        int i = 0;
        while (temp != null) {
            prev = temp;
            temp = temp.next;
            map.put(i++, temp);
        }
        return map.get(i + 1 - (k + 1));
    }

    //todo 双指针--快慢指针  保持步长一直为k，直到fast走完，返回slow即可
    public static ListNode getKthFromEnd2(ListNode head, int k) {
        ListNode fast = head;
        ListNode slow = head;
        //1--2--3--4--5
        //k=3
        while (fast != null && k > 0) {
            fast = fast.next;
            k--;
        }
        //fast=3
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }

    // 1-->2-->3-->4-->5
    // 2-->1-->3-->4-->5
    // 3-->2-->1-->4-->5
    // 4-->3-->2-->1-->5
    // 5-->4-->3-->2-->1
    public static void main(String[] args) {

    }


    public static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

}
